"""

eq_set 代表布尔方程组
eq_value 代表布尔方程组中方程的值
eq 代表方程
term 代表方程中的项

五大模块：
1. 生成方程组模块
2. 优化模块
3. 暴力求解模块
4. 无解/多解模块
5. 其他功能模块


"""
import random
from time import time
import multiprocessing as mp

class BoolEquations:
    """
        生成方程组
    """

    def __init__(self, num_variable):
        self.num_variable = num_variable
        # 方程组
        self.eq_set = []
        # 方程式右边的值
        self.eq_value = []
        self.num_cores = 1 if num_variable < 6 else 16
        # 暴力破解的结果
        self.result_set = []

    def run(self):
        """
            功能：运行，得出最终方程组
        """
        self.random_equations()
        self.optimize()
        self.exhaustion()

        while len(self.result_set) == 0:
            self.no_solution()
            self.exhaustion()
        while len(self.result_set) > 1:
            self.multiple_solutions()
            self.exhaustion()
    
    def run_other(self):
        """
            功能：运行非本程序生成的方程组
        """
        self.optimize()
        self.exhaustion()

        while len(self.result_set) == 0:
            self.no_solution()
            self.exhaustion()
        while len(self.result_set) > 1:
            self.multiple_solutions()
            self.exhaustion()

        return self.eq_set, self.eq_value

    # ==============================
    # 生成方程组模块
    # random_equations()
    # ==============================
    def random_equations(self):
        '''
            功能：随机生成布尔方程组
            布尔方程组格式如下：
            x1 + x2 = 0
            x1 * x2 = 1
            eq_set = [[1, 2], [(1, 2)]] => 内部列表[1, 2]表示x1 + x2, 元组(1, 2)表示x1 * x2
            eq_value = [0, 1]
        '''
        # 一个方程式最多有most_items项
        # if self.num_variable > 10:
        #     most_items = self.num_variable*2
        # else:
        most_items = int(self.num_variable*(self.num_variable+1)*0.5)
        # 生成一变元集合
        list_one = [i for i in range(self.num_variable)]
        # 生成二变元集合
        list_two = [(i, j) for i in range(self.num_variable) for j in range(i, self.num_variable)]
        # 所有元素列表
        list_all_elem = list_one + list_two

        #随机生成方程组
        for _ in range(self.num_variable):
            random.shuffle(list_all_elem)
            # 设置随机数种子
            random.seed(time())
            num = random.randint(1,most_items)
            self.eq_set.append(list_all_elem[:num])
        self.eq_value = [random.randint(0,1) for _ in range(self.num_variable)]

    # ==============================
    # 优化模块
    # optimize()
    #   --delete_none()
    #   --xx_to_x()
    #   --delete_same()
    # ==============================
    def delete_none(self):
        '''
            功能：删除方程组中为空的方程 => []
        '''
        for idx in range(len(self.eq_set)-1,-1,-1):
            if self.eq_set[idx] == []:
                #delete_index = self.eq_set.index(eq)
                self.eq_set.pop(idx)
                self.eq_value.pop(idx)

    def xx_to_x(self):
        """
            功能：优化x^2 -> x
        """
        for eq in self.eq_set:
            for term_idx in range(len(eq)):
                if type(eq[term_idx]) == tuple and eq[term_idx][0] == eq[term_idx][1]:
                    eq[term_idx] = eq[term_idx][0]

    def delete_same(self):
        """
            功能；删除重复项
            由于一个方程只能出现重复个数为2的项，所以仅需将重复项全删 x+x=0
        """
        for eq in self.eq_set[::-1]:
            for term in eq[::-1]:
                if eq.count(term) > 1:
                    for _ in range(2):
                        eq.remove(term)
        
        # 删除方程组中为空的方程
        self.delete_none()

    """
    def insertion_sort(self):
        '''
        功能：利用直接插入排序按照 方程长度 排序方程组
        '''
        for i in range(len(self.eq_set)):
            preIndex = i-1
            current = self.eq_set[i]
            current_value = self.eq_value[i]
            while preIndex >= 0 and len(self.eq_set[preIndex]) > len(current):
                self.eq_set[preIndex+1] = self.eq_set[preIndex]
                self.eq_value[preIndex+1] = self.eq_value[preIndex]
                preIndex-=1
            self.eq_set[preIndex+1] = current
            self.eq_value[preIndex+1] = current_value


    def delete_in(self):
        '''
            功能：删除各个方程的相同的项
        '''
        answer = self.result_set[0]
        self.eq_set.sort(key=len)
        for i in range(len(self.eq_set)):
            for j in range(len(self.eq_set)):
                # 同一方程
                if i == j:
                    continue
                for term_i in self.eq_set[i]:
                    idx = self.eq_set[i].index(term_i)
                    if idx >= len(self.eq_set[i])/2:
                        break
                    if term_i in self.eq_set[j]:
                        self.eq_set[j].remove(term_i)
                        #index = eq_set.index(term_i)
                        if type(term_i) == int:
                            value = answer[term_i]
                        elif type(term_i) == tuple:
                            value = answer[term_i[0] and term_i[1]]
                        if value == 0:
                                pass
                        elif value == 1:
                            if self.eq_value[j] == 0:
                                self.eq_value[j] = 1
                            elif self.eq_value[j] == 1:
                                self.eq_value[j] = 0
        self.delete_none()
    """

    def delete_include(self):
        '''
            功能：删除被包含方程
        '''
        self.eq_set.sort(key=len)
        for i in range(len(self.eq_set)):
            for j in range(len(self.eq_set)):
                # 同一方程
                if i == j:
                    continue
                inbool = 0
                count = 0
                for term_i in self.eq_set[i]:
                    if term_i in self.eq_set[j]:
                        count += 1
                if count == len(self.eq_set[i]):
                    inbool = 1
                if inbool == 1:
                    for term_i in self.eq_set[i]:
                        self.eq_set[j].remove(term_i)
                        #index = eq_set.index(term_i)
                        value = self.eq_value[i]
                        if value == 0:
                            pass
                        elif value == 1:
                            if self.eq_value[j] == 0:
                                self.eq_value[j] = 1
                            elif self.eq_value[j] == 1:
                                self.eq_value[j] = 0
        self.delete_none()

    def optimize(self):
        '''
            功能：优化布尔方程组
        '''
        # 删除方程组中为空的方程
        self.delete_none()
        # 优化x^2 -> x
        self.xx_to_x()
        # 删除重复项
        self.delete_same()
        # 删除被包含
        self.delete_include()
        # 按照方程长度排序
        self.eq_set.sort(key=len)


    # ==============================    
    # 暴力求解模块
    # exhaustion()
    # base_exhaustion()
    # param_list()
    # ==============================
    def exhaustion(self):
        """
            功能：暴力破解布尔方程组
        """
        pool = mp.Pool(self.num_cores)
        params = self.param_list()
        results_object = [pool.apply_async(self.base_exhaustion, args=(param,)) for param in params]
        self.result_set = [res for p in results_object for res in p.get()]


    def base_exhaustion(self,param):
        """
        功能：多进程暴力破解布尔方程组
        """
        result_temp = []
        test_answer = param[0]
        while test_answer != param[1]:
            count = 0
            for eq in self.eq_set:
                idx_eq = self.eq_set.index(eq)
                temp = 0
                for term in eq:
                    if type(term) == int:
                        temp += int(test_answer[term])
                    elif type(term) == tuple:
                        temp += int(test_answer[term[0]]) and int(test_answer[term[1]])
                if temp%2 == self.eq_value[idx_eq]:
                    count += 1
            if count == len(self.eq_set):
                result_temp.append(test_answer[::-1])
            
            temp2 = int(test_answer, 2) + 1
            test_answer = str('{:0{}b}'.format(temp2, self.num_variable))

        return result_temp

    def param_list(self):
        """
        功能：生成多进程列表
        """
        num = int((2**self.num_variable)/self.num_cores)
        params = []
        for i in range(self.num_cores):
            temp = []
            start = str('{:0{}b}'.format(num*i, self.num_variable))
            end = str('{:0{}b}'.format(num*(i+1), self.num_variable))
            temp.append(start)
            temp.append(end)
            params.append(temp)
        return params

    # ==============================    
    # 无解/多解模块
    # no_solution()
    # multiple_solutions()
    #   get_one_eq()
    # ==============================

    def no_solution(self):
        """
        功能：处理无解情况
        """
        pool = mp.Pool(self.num_cores)
        params = self.param_list()
        results = [pool.apply_async(self.base_no_solution, args=(param,)) for param in params]
        #eq_delete = [res for p in results for res in p.get()]
        eq_delete_temp = [p.get() for p in results]
        # 获取长度最短的列表
        eq_delete = min(eq_delete_temp, key=len)
        eq_delete.sort(reverse=True)
        for i in eq_delete:
            self.eq_set.pop(i)
            self.eq_value.pop(i)

    def base_no_solution(self, param):
        '''
        功能: 多进程处理无解情况
        '''
        eq_delete = [i for i in range(len(self.eq_set))]
        
        test_answer = param[0]
        while test_answer != param[1]:
            result_temp = []
            for eq in self.eq_set:
                temp1 = 0
                idx_eq = self.eq_set.index(eq)
                for term in eq:
                    if type(term) == int:
                        temp1 += int(test_answer[term])
                    elif type(term) == tuple:
                        temp1 += int(test_answer[term[0]]) and int(test_answer[term[1]])

                if temp1%2 != self.eq_value[idx_eq]:
                    result_temp.append(idx_eq)

            if len(result_temp) < len(eq_delete):
                eq_delete = result_temp[:]
            
            temp2 = int(test_answer, 2) + 1
            test_answer = str('{:0{}b}'.format(temp2, self.num_variable))

        return eq_delete


    def get_one_eq(self):
        # 一个方程式最多有most_items项
        #most_items = int(self.num_variable*(self.num_variable+1)*0.5)
        one = [[i,k] for i in range(self.num_variable) for k in [0, 1]]
        # 生成二变元集合
        two = [[(i, j),k] for i in range(self.num_variable) for j in range(i+1, self.num_variable) for k in [0, 1]]
        # 所有元素列表
        all_elem = one + two
        eq_set_add = []
        eq_value_add = 0
        result_set = [term[::-1] for term in self.result_set]

        for eq in all_elem:
            result_current = []
            for test_answer in result_set:
                temp1 = 0
                if type(eq[0]) == int:
                    temp1 += int(test_answer[eq[0]])
                elif type(eq[0]) == tuple:
                    temp1 += int(test_answer[eq[0][0]]) and int(test_answer[eq[0][1]])
                if temp1%2 == eq[1]:
                    result_current.append(test_answer[::])
            if len(result_current) == 1:
                eq_set_add.append(eq[0])
                eq_value_add = eq[1]
                break
        """
        result_set = self.result_set
        result_current = []
        while True:
            # print(1)
            # 设置随机数种子
            random.seed(time())
            num = random.randint(1, most_items)
            random.shuffle(all_elem)
            eq_set_add = one[:num]
            eq_value_add = random.randint(0,1)

            for test_answer in result_set:
                temp1 = 0
                for term in eq_set_add:
                    if type(term) == int:
                        temp1 += int(test_answer[term])
                    elif type(term) == tuple:
                        temp1 += int(test_answer[term[0]]) and int(test_answer[term[1]])
                if temp1%2 == eq_value_add:
                    result_current.append(test_answer[::-1])

            result_temp = list(set(result_current).intersection(set(result_set)))

            if len(result_temp) == 1:
                break
        """ 
            
        return eq_set_add, eq_value_add

    def multiple_solutions(self):
        '''
        功能：处理方程组多解情况
        '''
        if len(self.eq_set) == self.num_variable:
            # 删除项最多的方程，即最后一个，因为方程组按照方程长度由小到大排列
            idx_delete = len(self.eq_set)-1
            self.eq_set.pop(idx_delete)
            self.eq_value.pop(idx_delete)
            # 寻找具有唯一解的一个方程
            eq_set_add, eq_value_add = self.get_one_eq()
            self.eq_set.append(eq_set_add)
            self.eq_value.append(eq_value_add)

        elif len(self.eq_set) < self.num_variable:
            # 寻找具有相同解的一个方程
            eq_set_add, eq_value_add = self.get_one_eq()
            self.eq_set.append(eq_set_add)
            self.eq_value.append(eq_value_add)

        self.optimize()


    # ==============================
    # 其他功能模块
    # split_intege()
    # print_equations()
    # ==============================
    
    def split_integer(self):
        """
            功能：将方程分组
        """
        num_group = 1
        num_per_group = []
        
        # 分几组
        while num_group*(num_group+1) < 2*len(self.eq_set):
            num_group += 1

        while num_group > 0:
            num_per_group.append(num_group)
            num_group -= 1
            if sum(num_per_group) >= len(self.eq_set):
                break
        num_per_group[-1] -= (sum(num_per_group) - len(self.eq_set))

        eq_per_group = []
        temp1, temp2 = 0, 0
        for i in num_per_group:
            temp1 += i
            eq_per_group.append(list(range(temp2,temp1)))
            temp2 = temp1
        return eq_per_group

    def print_equations(self):
        '''
            功能：打印方程组
        '''
        self.eq_set.sort(key=len)
        print("============方程组============")
        for eq in self.eq_set:
            print(eq, end='\n')
        print("============方程的值==========")
        print(self.eq_value)
        print("==============================")
